/** \file    segmbasic.h
  * \brief   Production of index map with connectivity information about indeces from arbitrary sources.
  * \date    2002
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/include/imglib/segmbasic.h,v 1.5 2006/01/15 22:05:16 cscom1r4 Exp $
  */

#ifndef _segmbasic_h_
#define _segmbasic_h_

#include "xtd/group.h"

namespace img {

//SC - Segment Checker - checks whether two pixels bolong to one segment or not

///simplest piece checker for segmentation as source (with possibility to unconnected segments to have the same color)
template <class R>
class simple_checker
{
public:
	simple_checker(R &r) : _r(r) {}
	bool top(size_t x, size_t y) const
		{ return _r(x,y-1) == _r(x,y); }
	bool left(size_t x, size_t y) const
		{ return _r(x-1,y) == _r(x,y); }
	bool top_left(size_t x, size_t y) const
		{ return _r(x-1,y-1) == _r(x,y); }
	bool top_right(size_t x, size_t y) const
		{ return _r(x+1,y-1) == _r(x,y); }
private:
	R &_r;
};

enum merge_dir {
	dirN=1, dirE=2, dirS=4, dirW=8,
	dirNE=16, dirSE=32,	dirNW=64, dirSW=128
};

inline merge_dir opposite(merge_dir x) {
	switch (x) {
	case dirN:
		return dirS;
	case dirS:
		return dirN;
	case dirW:
		return dirE;
	case dirE:
		return dirW;
	}
	return merge_dir(0);
}

///checks community of two points by looking into dir_image
template <class R> //R = img::image<unsigned char>
class merge_dir_checker
{
public:
	merge_dir_checker(const R &d) : _d(d) {}
	bool top(size_t x, size_t y) const
		{ return _d(x,y-1)&dirS || _d(x,y)&dirN; }
	bool left(size_t x, size_t y) const
		{ return _d(x-1,y)&dirE || _d(x,y)&dirW; }
	bool top_left(size_t x, size_t y) const
		{ return _d(x-1,y-1)&dirSE || _d(x,y)&dirNW; }
	bool top_right(size_t x, size_t y) const
		{ return _d(x+1,y-1)&dirSW || _d(x,y)&dirNE; }
private:
	const R &_d;
};

///typical superclass of objects in PV for segmbasic
template <class T=size_t>
struct segm_piece: public xtd::patch<T>
{
	segm_piece() : pixels(0) {}
	size_t pixels;

	void insert(size_t /*x*/, size_t /*y*/)
		{ ++pixels; }
	void subdue(segm_piece &child)
		{ pixels += child.pixels; }
};

///PV - (vector) container of output pieces, descendants of xtd::patch<> with 'insert' member,
///each piece describes area with
template <class RI, class PV, class SC>
void segmbasic8(RI& index_map, PV& piece_vector, SC& segm_checker)
{
	size_t w = index_map.width(), h = index_map.height();

	typedef PV::value_type piece; //element of segment
	piece_vector.clear();

	RI::iterator ii(index_map.begin());
	//first pass: write into index_map piece indexes
	for (; ii != index_map.end(); ++ii) {
		const size_t x = ii.x();
		const size_t y = ii.y();
		int current_index=-1, top_brother_index=-1, left_brother_index=-1;
		int nw_brother_index=-1, ne_brother_index=-1;

		if( y!=0 && segm_checker.top(x, y) )
			current_index = top_brother_index = ii.rel(0,-1);
		if( x!=0 && segm_checker.left(x, y) )
			current_index = left_brother_index = ii.rel(-1,0);
		if( x!=0 && y!=0 && segm_checker.top_left(x, y) )
			current_index = nw_brother_index = ii.rel(-1,-1);
		if( x!=w-1 && y!=0 && segm_checker.top_right(x, y) )
			current_index = ne_brother_index = ii.rel(1,-1);

		if (current_index == -1) {
			//no brothers - new segment
			current_index = piece_vector.size();
			piece_vector.push_back(piece());
		} else {
			if( left_brother_index!=-1 && left_brother_index!=current_index )
				xtd::union_sets(piece_vector, current_index, left_brother_index);
			if( top_brother_index!=-1 && top_brother_index!=current_index )
				xtd::union_sets(piece_vector, current_index, top_brother_index);
			if( nw_brother_index!=-1 && nw_brother_index!=current_index )
				xtd::union_sets(piece_vector, current_index, nw_brother_index);
			if( ne_brother_index!=-1 && ne_brother_index!=current_index )
				xtd::union_sets(piece_vector, current_index, ne_brother_index);
			current_index = xtd::find_root_idx(piece_vector, current_index);
		}

		piece_vector[*ii = current_index].insert(x,y);
	}
}

template <class RI, class PV, class SC>
void segmbasic4(RI& index_map, PV& piece_vector, SC& segm_checker)
{
	size_t w = index_map.width(), h = index_map.height();

	typedef PV::value_type piece; //element of segment
	piece_vector.clear();

	RI::iterator ii(index_map.begin());
	//first pass: write into index_map piece indexes
	for (; ii != index_map.end(); ++ii) {
		const size_t x = ii.x();
		const size_t y = ii.y();
		int current_index=-1, top_brother_index=-1, left_brother_index=-1;

		if( y!=0 && segm_checker.top(x, y) )
			current_index = top_brother_index = ii.rel(0,-1);
		if( x!=0 && segm_checker.left(x, y) )
			current_index = left_brother_index = ii.rel(-1,0);

		if (current_index == -1) {
			//no brothers - new segment
			current_index = piece_vector.size();
			piece_vector.push_back(piece());
		} else {
			if( left_brother_index!=-1 && left_brother_index!=current_index )
				xtd::union_sets(piece_vector, current_index, left_brother_index);
			if( top_brother_index!=-1 && top_brother_index!=current_index )
				xtd::union_sets(piece_vector, current_index, top_brother_index);
			current_index = xtd::find_root_idx(piece_vector, current_index);
		}

		piece_vector[*ii = current_index].insert(x,y);
	}
}

///rewrites index map of pieces with indeces of pieces' roots
template <class RI, class PV>
void rewrite(RI& index_map, PV& piece_vector)
{
	RI::iterator ii(index_map.begin());
	for (; ii != index_map.end(); ++ii)
		*ii = xtd::find_root_idx(piece_vector, *ii);
}

struct numbered_piece : public xtd::patch<size_t>
{
	numbered_piece() : num(-1) { }
	int num;
	void insert(size_t /*x*/, size_t /*y*/)	{ }
};

/// rewrites index map of pieces with sequential numbers from 0 to segments-1, returns segments count;
/// 'num' attributes of pieces must have negative values before the function call
template <class RI, class PV>
size_t rewrite_seq(RI & index_map, PV & piece_vector)
{
	size_t curr = 0;
	RI::iterator ii(index_map.begin());
	for (; ii != index_map.end(); ++ii) {
		typename PV::value_type & val = xtd::find_root(piece_vector, *ii);
		if (val.num < 0)
			val.num = curr++;
		*ii = val.num;
	}
	return curr;
}

///relabel = (segmbasic4 + rewrite_seq), gives to disjoint areas sequential numbers from 0 to segments-1, returns segments count
template <class RI, class SC>
size_t relabel(RI & index_map, SC & segm_checker)
{
	std::vector<numbered_piece> piece_vector;
	img::segmbasic4(index_map, piece_vector, segm_checker);
	return img::rewrite_seq(index_map, piece_vector);
}

///uses temporary storage during work, this is required when segm_checker depends on index_map inside
template <class RI, class SC>
size_t relabel_tmp_storage(RI & index_map, SC & segm_checker)
{
	RI tmp(index_map.dim());
	size_t scount = relabel(tmp, segm_checker);
	tmp.swap(index_map);
	return scount;
}

} //namespace img

#endif //_segmbasic_h_
